/*
就是560的变形
🧠 抽象视角：树路径 = 多个数组
在题目560中：

你有一个数组 nums，每个子数组是连续的一段
你要找的是：有多少个子数组的和为 k

在树题（路径和 III）中：

每条从某个节点出发向下走的路径，可以看作一个数组
每个路径是从某个祖先到当前节点的连续节点值序列
你要找的是：有多少条这样的“路径数组”的某一段和为 targetSum
*/


//1.dfs
class Solution {
public:
    int act_pace(TreeNode* root, long long curSum, int targetSum, int& ret) {
        if(root==nullptr) return 0;
        curSum += root->val;
        if(curSum == targetSum) ret++;

        act_pace(root->left, curSum, targetSum, ret);
        act_pace(root->right, curSum, targetSum, ret);

        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return 0;

        int ret=0;
        act_pace(root, 0, targetSum, ret); //返回当前节点满足的个数ret
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};
//2.前缀和
class Solution {
public:
    int countPaths(TreeNode* node, int targetSum,
                   unordered_map<long long, int>& prefixCount, //哈希表一定要传引用，不然构造开销很大
                   long long currSum) {
        if (!node) return 0;

        currSum += node->val;
        int pathCount = prefixCount[currSum - targetSum];  // 下标访问在不存在时会返回 0

        prefixCount[currSum]++;  // 登记当前前缀
        pathCount += countPaths(node->left, targetSum, prefixCount, currSum);
        pathCount += countPaths(node->right, targetSum, prefixCount, currSum);
        prefixCount[currSum]--;  // 回溯撤销

        return pathCount;
    }

    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> prefixCount;
        prefixCount[0] = 1;  // 第0个的元素前缀和为0
        return countPaths(root, targetSum, prefixCount, 0);
    }
};
/*
//自己做法，2是优化后的，时间空间复杂度都一样
class Solution {
public:
    int act(TreeNode* root, int& targetSum, unordered_map<long long, int>& hashmap, 
            long long  cur) {
        
        if(!root) return 0;
        int count=0;
        cur += root->val;
        if(hashmap.count(cur-targetSum)) {
            count+=hashmap[cur-targetSum];
        }
        hashmap[cur]++;
        count += act(root->left, targetSum, hashmap, cur);
        count += act(root->right, targetSum, hashmap, cur);
        hashmap[cur]--;
        return count;
    }


    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long long, int> hashmap;
        hashmap[0]=1;
       
       long long  cur=0;
       return act(root, targetSum, hashmap, cur);
        
    }
};

*/
